package practice1_100;

import java.sql.Time;
import java.util.Arrays;
import java.util.Date;

public class Practice198 {
    int[] count;

    public int rob(int[] nums) {
        if (nums.length == 0) return 0;
        int sum = 0;

        //初始化记忆数组
        count = new int[nums.length];
        Arrays.fill(count, -1);

        sum = repeat(nums, nums.length - 1);
        return sum;
    }

    public int repeat(int[] nums, int index) {
        if (index == 0) return nums[index];
        if (index < 0) return 0;
        if (count[index] != -1) return count[index];
        count[index] = Math.max(repeat(nums, index - 2) + nums[index], repeat(nums, index - 1));
        return count[index];
    }


    public int rob1(int[] nums) {
        if (nums.length == 0) return 0;
        int sum = 0;

        //初始化记忆数组

        sum = repeat1(nums, nums.length - 1);
        return sum;
    }

    public int repeat1(int[] nums, int index) {
        if (index == 0) return nums[index];
        if (index < 0) return 0;
        return   Math.max(repeat1(nums, index - 2) + nums[index], repeat1(nums, index - 1));
    }

    public static void main(String[] args) {
        long date1= new Date().getTime();
        Practice198 practice198 = new Practice198();
        int a = practice198.rob(new int[]{114, 117, 207, 117, 235, 82, 90, 67, 143, 146, 53, 108, 200, 91, 80, 223, 58, 170, 110, 236, 81, 90, 222, 160, 165, 195, 187, 199, 114, 235, 197, 187, 69, 129, 64, 214, 228, 78, 188, 67, 205, 94, 205, 169, 241, 202, 144, 240,114, 117, 207, 117, 235, 82, 90, 67, 143, 146, 53, 108, 200, 91, 80, 223, 58, 170, 110, 236, 81, 90, 222, 160, 165, 195, 187, 199, 114, 235, 197, 187, 69, 129, 64, 214, 228, 78, 188, 67, 205, 94, 205, 169, 241, 202, 144, 240,114, 117, 207, 117, 235, 82, 90, 67, 143, 146, 53, 108, 200, 91, 80, 223, 58, 170, 110, 236, 81, 90, 222, 160, 165, 195, 187, 199, 114, 235, 197, 187, 69, 129, 64, 214, 228, 78, 188, 67, 205, 94, 205, 169, 241, 202, 144, 240,114, 117, 207, 117, 235, 82, 90, 67, 143, 146, 53, 108, 200, 91, 80, 223, 58, 170, 110, 236, 81, 90, 222, 160, 165, 195, 187, 199, 114, 235, 197, 187, 69, 129, 64, 214, 228, 78, 188, 67, 205, 94, 205, 169, 241, 202, 144, 240,114, 117, 207, 117, 235, 82, 90, 67, 143, 146, 53, 108, 200, 91, 80, 223, 58, 170, 110, 236, 81, 90, 222, 160, 165, 195, 187, 199, 114, 235, 197, 187, 69, 129, 64, 214, 228, 78, 188, 67, 205, 94, 205, 169, 241, 202, 144, 240});
        System.out.println(a);
        System.out.println(new Date().getTime()-date1);
    }





    //优化算法
//    public int rob1(int[] nums) {
//        if (nums.length == 0) return 0;
//        int sum = 0;
//        for (int i = 0; i < nums.length; i++) {
//            sum = Math.max(nums[i], );
//        }
//    }

}
